from Sorts.MergeSort import mergesort

class Solution(object):
    # 排序 + 双指针
    def threeSum(self, nums):  # Time: O(n^2); Space: O(log n)
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) < 3: return []
        
        res = []
        nums = mergesort(nums)
        for i, n in enumerate(nums):
            l = i + 1
            r = len(nums) - 1
            while l < r:
                if nums[l] + nums[r] < -n:
                    l += 1
                elif nums[l] + nums[r] > -n:
                    r -= 1
                else:
                    if res == [] or [n, nums[l], nums[r]] not in res:
                        res.append([n, nums[l], nums[r]])
                    l += 1
                    r -= 1
        return res


if __name__ == "__main__":
    soln = Solution()
    print(soln.threeSum([]))
    print(soln.threeSum([1]))
    print(soln.threeSum([1,-1]))
    print(soln.threeSum([-1,0,1,2,-1,-4]))
    print(soln.threeSum([-1,0,1,2,-1,-4,4,1]))
    print(soln.threeSum([-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]))
